The present invention relates to a packet transfer method and apparatus and a packet communication system.
(1) Arrangement of Conventional Network
FIG. 15 shows the arrangement of a network conventionally used for packet communication. A description will be made below by exemplifying, as a packet transfer apparatus, a router apparatus for transferring an IP (Internet Protocol) packet. As shown in FIG. 15, a plurality of router apparatuses for relaying a packet are arranged in the network. Four router apparatuses 1a to 1d are exemplified in FIG. 15. These router apparatuses are connected through transmission paths. For example, the router apparatus 1a and router apparatus 1b are connected through a transmission path 2ab. The remaining router apparatuses are connected through transmission paths 2ac, 2ad, 2bc, 2bd, and 2cd. Each router apparatus is connected to one or a plurality of user LANs (Local Area Networks) as an example of an access network. Each router apparatus and the user LANs are connected through access lines. FIG. 15 exemplifies a form in which two user LANs are connected to each router apparatus. For example, user LANs 3a1 and 3a2 are connected to the router apparatus 1a through access lines 4a1 and 4a2, respectively. This also applies to the router apparatuses except the router apparatus 1a: user LANs 3b1 and 3b2, 3c1 and 3c2, and 3d1 and 3d2 are connected to the remaining router apparatuses through access lines 4b1 and 4b2, 4c1 and 4c2, and 4d1 and 4d2, respectively. Each user LAN is connected to one or a plurality of host terminals. FIG. 15 illustrates only a transmission-source host 5a1 and destination host 5d1 connected to the user LANs 3a1 and 3d1, respectively. The remaining host terminals are not shown in FIG. 15.
Assume that an IP packet is to be transmitted from the transmission-source host 5a1 to the destination host 5d1 through a transfer route 6 in the arrangement shown in FIG. 15. On the transmission path or access line, an IP packet is transferred in the form of layer 1 frame. However, in order to avoid cumbersomeness, an expression “an IP packet is transferred on the transmission path or access line” may be used in the following description. When the transfer route 6 is used, an IP packet generated by the transmission-source host 5a1 is converted into the format of layer 1 frame and sent to the user LAN 3a1 and then to the router apparatus 1a through the access line 4a1.
The router apparatus 1a determines the transfer path of the IP packet on the basis of a destination address described in the header of the IP packet in the received layer 1 frame, thereby specifying the router apparatus or user LAN to which the IP packet should be transferred. At the same time, the router apparatus 1a specifies the transmission path or access line as a transfer path corresponding to the specified router apparatus or user LAN. In the example shown in FIG. 15, the transmission path 2ad and router apparatus 1d are specified as the transfer destination of the IP packet. The router apparatus 1a sends the layer 1 frame containing the IP packet onto the transmission path 2ad. The router apparatus 1d transfers the IP packet, like the router apparatus 1a. Consequently, the IP packet is transferred to the user LAN at the destination through the access line 4d1 and finally transferred to the destination host 5d1 in this user LAN.
(2) Arrangement of Conventional Router Apparatus
The arrangement and operation of each router apparatus shown in FIG. 15 will be described next. FIG. 16 shows the arrangement of a router apparatus. The router apparatus comprises one or a plurality of input interface sections 10-1 to 10-N (N: natural number), one or a plurality of output interface sections 11-1 to 11-N, a switch scheduler section 12, and a crossbar switch section 13. Each input interface section comprises a layer 1/2 processing section 14, IP layer processing section 15, packet segmenting section 16, and route search table 17. The input interface sections 10-1 to 10-N are assigned unique input interface numbers “1” to “N”, respectively. On the other hand, each output interface section comprises a packet reassembler section 18, IP layer processing section 19, and layer 1/2 processing section 20. The output interface sections 11-1 to 11-N are assigned unique output interface numbers “1” to “N”.
One of the transmission paths or access lines shown in FIG. 15 is connected to the layer 1/2 processing section 14 in each input interface section. For example, the layer 1/2 processing section 14 in the input interface section 10-1 is connected to the access line 4a2 shown in FIG. 15, and the layer 1/2 processing section 14 in the input interface section 10-2 is connected to the transmission path 2ac. The layer 1/2 processing section 14 has a function of terminating the layer 1/2 protocol of a transmission path or access line that is to be terminated at the input interface section to which the layer 1/2 processing section 14 belongs, and transfers the terminated IP packet to the IP layer processing section 15.
The IP layer processing section 15 looks up the header of the IP packet transferred from the layer 1/2 processing section 14 and processes the IP layer. A detailed description of this IP layer processing will be omitted herein because it is an existing technique and has no relation to the present invention. The packet segmenting section 16 segments the IP packet transferred from the IP layer processing section 15 into fixed-length device cells defined in the router apparatus and sends the device cells to the crossbar switch section 13. That is, this fixed length corresponds to the length of the switching unit of the router apparatus. Simultaneously, the packet segmenting section 16 sends a transfer request signal 21 to the switch scheduler section 12 to transfer the transferred IP packet to one of the output interface sections 11-1 to 11-N.
The switch scheduler section 12 is a functional block of performing switch setting in the crossbar switch section 13. The transfer request signal 21 and transfer reply signal 22 are exchanged between the switch scheduler section 12 and the packet segmenting section 16 in each of the input interface sections 10-1 to 10-N through a bi-directional signal line. That is, the transfer request signal 21 is sent from the packet segmenting section 16 to the switch scheduler section 12, while the transfer reply signal 22 is sent from the switch scheduler section 12 to the packet segmenting section 16. Upon receiving the transfer request signal 21 transmitted from the packet segmenting section 16, the switch scheduler section 12 calculates optimum switch setting in the crossbar switch section 13 and sends a switch setting signal 23 to the crossbar switch section 13.
The crossbar switch section 13 connects one of the input interface sections 10-1 to 10-N to one of the output interface sections 11-1 to 11-N on the basis of the transmitted switch setting signal 23. In each of the output interface sections 11-1 to 11-N, the packet reassembler section 18 stacks the fixed-length device cells transferred from one of the input interface sections 10-1 to 10-N through the crossbar switch section 13 to reassemble the cells into the original IP packet (i.e., the IP packet terminated by the layer 1/2 processing section 14) and transfers the IP packet to the IP layer processing section 19. The IP layer processing section 19 looks up the header of the IP packet transferred from the packet reassembler section 18 and performs processing associated with the IP layer, and then transfers the IP packet to the layer 1/2 processing section 20.
The layer 1/2 processing section 20 attaches the header of layer 1/2 to the transferred IP packet to construct a layer 1 frame and transfers it to the output path as a transmission path or access line. More specifically, as in the input interface sections 10-1 to 10-N, one of the transmission paths or access lines shown in FIG. 15 is connected to the layer 1/2 processing section 20 in each output interface section. For example, the layer 1/2 processing section 20 in the output interface section 11-1 is connected to the access line 4a2 shown in FIG. 15, and the layer 1/2 processing section 20 in the output interface section 11-2 is connected to the transmission path 2ac. 
(3) Operation of Conventional Router Apparatus
A detailed operation of the router apparatus shown in FIG. 16 will be described next in detail. In this case, the signal transmitted on the transmission path or access line shown in FIG. 15 has a format shown in FIG. 17. More specifically, as described above, a layer 1 frame 30 is transmitted on the transmission path or access line. A layer 1 header 31 is periodically inserted into the layer 1 frame 30. With this layer 1 header 31, the function of the layer 1, i.e., the OAM (Operation Administration and Maintenance) function used to monitor bit synchronization, byte synchronization, frame synchronization, line state, or error rate is realized by the layer 1/2 processing section 14.
A layer 2 frame 33 is contained in a layer 1 payload 32. The variable-length layer 2 frame 33 is transferred through this portion. The layer 2 frame 33 is constructed by sandwiching a layer 2 payload 36 by a layer 2 header 34 and layer 2 trailer 35. An IP packet 37 is put on the layer 2 payload 36. The IP packet 37 is constructed by a header 38 and payload 39.
The layer 1/2 processing section 14 shown in FIG. 16 performs layer 1 processing on the signal input from the transmission path or access line and then looks up the layer 2 header 34 and layer 2 trailer 35 contained in the layer 2 frame 33 and executes layer 2 processing. A detailed description of the layer 1 processing and layer 2 processing will be omitted because they are existing techniques and have no direct relation to the present invention. After that, the layer 1/2 processing section 14 extracts the IP packet 37 contained in the layer 2 payload 36 and transfers it to the IP layer processing section 15.
The IP layer processing section 15 looks up the header 38 of the transferred IP packet 37 and executes IP layer processing such as IP header validity determination or abnormal IP packet reception processing. In addition, the route information in the route search table 17 is searched in accordance with the contents of the destination address field contained in the header 38. With this search operation, the IP layer processing section 15 specifies the router apparatus or user LAN to which the IP packet is to be transferred next. Simultaneously, the IP layer processing section 15 specifies the output interface number (i.e., “1” to “N”) assigned to one of the output interface sections 11-1 to 11-N, which corresponds to the router apparatus or user LAN, and transfers the IP packet (“data signal” in FIG. 16) and output interface number to the packet segmenting section 16.
The packet segmenting section 16 segments the IP packet 37 transferred from the IP layer processing section 15 into fixed-length device cells 40, as shown in FIG. 17, and stores them in the payload portion. Additionally, the packet segmenting section 16 attaches a cell header 41 to each device cell 40. Not only the output interface number of the transfer destination but also the input interface number (for example, “2” for the packet segmenting section 16 in the input interface section 10-2) assigned to the input interface section of its own as the transmission source is written in the cell header 41.
The packet segmenting section 16 incorporates memories (not shown) in units of output interface numbers. The segmented device cells 40 are stored in a memory corresponding to the output interface number. The packet segmenting section 16 also sends the transfer request signal 21 to the switch scheduler section 12 to transfer the device cells 40 stored in the memory to one of the output interface sections 11-1 to 11-N, which corresponds to the output interface number written in the cell headers 41.
Upon receiving the transfer request signal 21 sent from one of the input interface sections 10-1 to 10-N, the switch scheduler section 12 calculates an appropriate combination of switch connections between the input interface section and the output interface section. Next, the switch scheduler section 12 returns the transfer reply signal 22 to the input interface sections 10-1 to 10-N to notify them of one of the output interface sections 11-1 to 11-N, to which the IP packet 37 is to be transferred. Upon receiving the transfer reply signal 22, the input interface sections 10-1 to 10-N sequentially transfer the device cells 40 having a fixed length to the crossbar switch section 13 to transfer them to the input interface section designed by the transfer reply signal 22. At the same time, the switch scheduler section 12 sends the switch setting signal 23 to the crossbar switch section 13.
On the basis of the received switch setting signal 23, the crossbar switch section 13 performs switch connection between the designated input interface section and the designated output interface section. Thus, the device cells 40 are sequentially transferred from the input interface sections 10-1 to 10-N to the output interface sections 11-1 to 11-N. The packet reassembler section 18 in the designated input interface section stores the device cells 40 transferred from the designated input interface section in one of internal memories (not shown) on the basis of the input interface number described in the cell headers 41. The packet reassembler section 18s stacks the device cells 40 to reassemble the cells into the original IP packet 37 from the payload portions excluding the cell headers 41 of the device cells 40, and transfers the IP packet 37 to the IP layer processing section 19.
The IP layer processing section 19 executes IP layer processing for the received IP packet 37 and then transfers it to the layer 1/2 processing section 20. The layer 1/2 processing section 20 stores the received IP packet 37 in the layer 2 payload 36 and attaches the layer 2 header 34 and layer 2 trailer 35 on both sides of the layer 2 payload 36 to construct the layer 2 frame 33. Next, the layer 1/2 processing section 20 stores the constructed layer 2 frame 33 in the layer 1 payload 32 and attaches the layer 1 header 31 on the front side of the layer 1 header 31 to construct a layer 1 frame 42. Then, the layer 1/2 processing section 20 sends the layer 1 frame 42 onto the transmission path or access line connected to the designated output interface section.
With the above operation, the IP packet transferred from a transmission path or access line to the router apparatus through a corresponding input interface is transferred onto a transmission path or access line corresponding to an output interface.
The following techniques are similar to the above technique. For example, in the above description, a variable-length packet is segmented into fixed-length cells. However, WO/26589 or Japanese Patent Laid-Open No. 7-245628 discloses a technique of multiplexing a short packet on a fixed-length packet (53-byte ATM [Asynchronous Transfer Mode] cell) and transferring it between nodes on a network. Japanese Patent Laid-Open No. 63-197148 discloses a technique of grouping short packets having the same destination into a long packet and transferring it on a network.
Problems of the above-described IP packet transfer using the conventional router apparatus will be described next.
(1) First Problem of Prior Art
As described above, the crossbar switch section 13 shown in FIG. 16 is a switch for processing the fixed-length device cell 40 as shown in FIG. 17. For this reason, when the transfer time unit of the device cell 40 is represented by “τ”, the switch connection operation of the crossbar switch section 13 must be switched every transfer time unit τ. Hence, the switch scheduler section 12 must calculate setting for the switch connection in the crossbar switch section 13 every time in the transfer time unit τ. This also applies to the above-described WO/26589 and Japanese Patent Laid-Open No. 7-245628. In these prior-art techniques, short ATM cells of 53 bytes are switched by packet switching.
To increase the switching capacity of the router apparatus, the number of interfaces in the input interface sections 10-1 to 10-N or output interface sections 11-1 to 11-N must be increased without changing the interface speed, or the interface speed must be increased without changing the number of interfaces. In the former case, the number of the input interface sections or output interface sections increases, and accordingly, the amount of calculation for switch connection setting increases. Since the device that implements the router apparatus has a limited ability, the amount of calculation processable within the range of transfer time unit τ (i.e., the calculation ability of the switch scheduler section 12) also has an upper limit. For this reason, the number of interfaces cannot be increased beyond a certain upper limit, and the switching capacity cannot be increased beyond a predetermined capacity, either.
When the latter of the above-described two measures is selected, the interface speed of the input interface section or output interface section is increased, and the transfer time unit τ of the device cell 40 becomes short in inverse proportion to the interface speed. This is equivalent to a decrease in calculation time for switch connection setting. After the interface speed is increased, calculation for switch connection setting can be executed for only a smaller number of interfaces within the defined transfer time unit τ. That is, in this case as well, it is difficult to increase the switching capacity. As described above, since the upper limit of the switching capacity or switching scale is determined by the length of the device cell 40, the switching capacity of the router apparatus cannot be increased beyond a predetermined capacity.
(2) Second Problem of Prior Art
As is mentioned in association with the first problem, when the fixed-length device cell 40 to be switched in the router apparatus is small, and the cell transfer time is short, the transfer time unit τ for defining the limit of the calculation time for switch connection setting in the switch scheduler section 12 becomes short (this also applies to the above-described WO/26589 and Japanese Patent Laid-Open No. 7-245628). The device cell 40 must inevitably have a predetermined length or more. Especially, in a large-scale router apparatus, when a device cell of 64 bytes (minimum length of an IP packet) or less is defined, the calculation time necessary for switch connection setting cannot be ensured. Many existing large-scale routers define a device cell longer than the minimum length of an IP packet, e.g., a 128- or 256-byte long cell. For this reason, the throughput of switching remarkably degrades depending on the distribution of lengths of transferred IP packets.
This will be described below in more detail. Assume that the size of the device cell 40 is 128 bytes, IP packets having the minimum length (i.e., 64 bytes) are continuously input to the input interface sections 10-1 to 10-N, and these IP packets are transferred to different output interface sections of the output interface sections 11-1 to 11-N. The packet segmenting section 16 and packet reassembler section 18 shown in FIG. 16 are provided originally for the purpose of segmenting a variable-length IP packet into the device cells 40 for the use in the router apparatus, causing the crossbar switch section 13 to switch the segmented device cells 40, and reassembling the IP packet from the switched device cells 40 in the output interface sections 11-1 to 11-N.
However, in the assumed situation above, since the IP packet itself is shorter than the device cell and therefore cannot be segmented, the device cell 40 must be transferred using the IP packet itself as its unit. For this reason, the payload region of the device cell 40 is partially unused. This unused region directly corresponds to the unused band of switching, so the throughput of switch operation is decreased by the amount of the unused region. For example, assume that 64-byte long packets PA, PB, and PC are sequentially input to one of the input interface sections of the router apparatus and transmitted to the packet segmenting section 16 in the input interface section, as shown in FIG. 18.
Since these IP packets are to be transferred to different output interface sections, and the size of the device cell 40 is 128 bytes, as shown in FIG. 18, each device cell 40 with an inserted IP packet undesirably keeps its 1/2 region i.e., 64-byte region (corresponding to a “free band” in FIG. 18) unused. In addition, since the speed of inputting an IP packet to the packet segmenting section 16 equals the speed of outputting each device cell 40 from the packet segmenting section 16, device cells corresponding to only 1/2 the input information amount can be output. Since 1/2 of IP packets input to the packet segmenting section 16 is discarded by the packet segmenting section 16, the throughput of switch operation decreases to 50%. The above-described Japanese Patent Laid-Open No. 63-197148 also suffers the same problem as described above because it is suggested that a routing processing means in a packet switching network actually segments a long packet into device cells and switches them.
(3) Third Problem of Prior Art
Generally, IP packets have variable lengths. When the packet segmenting section 16 in the router apparatus segments an IP packet into the fixed-length device cells 40, the device cell containing the end portion of the IP packet has a free region. For example, when the single IP packet 37 is segmented into device cells 40a to 40f, as shown in FIG. 19, the device cell 40f at the end portion has a free portion (corresponding to the “free region” in FIG. 19). Padding is necessary for this free portion. When the series of device cells 40a to 40f are transferred to the crossbar switch section 13, the free portion contained in the final device cell 40f always serves an unused region to decrease the switch transfer capacity.
For example, assume a case wherein the length of the device cell is 128 bytes, and only 129-byte long IP packets are generated. In this case, the switch transfer capacity decreases to 129/(128×2)≈50%. This problem also occurs in the above-described WO/26589 and Japanese Patent Laid-Open No. 7-245628 in which switching is executed in units of ATM cells, and the above-described Japanese Patent Laid-Open No. 63-197148 in which it is suggested that a routing processing means in a packet switching network actually segments a long packet into device cells and switches them.